'''
This file is a RBTree Library complete by Zhengbo Wang. 

'''
class RBNode(object):
    def __init__(self, color='B'):
        self.val = None
        self.left = None
        self.right = None
        self.parent = None
        self.color = color
        
    def is_black(self):
        return self.color == 'B'
    

class RBTree(object):
    def __init__(self):        
        self.__nil = RBNode()
        self.root = RBNode()
        self.root.left = self.__nil
        self.root.right = self.__nil
    
    def search(self, num):
        x = self.root
        while x.val != num:
            if num > x.val:
                x = x.right
            else:
                x = x.left
        assert x!=self.__nil, 'the element is not in RBTree'
        return x
    
    def insert(self, node):
        '''
        Insert a node
        '''
        z = node
        z.left = self.__nil
        z.right = self.__nil
        x = self.root
        
        while x != self.__nil:
            if z.val >= x.val:
                if x.right == self.__nil:
                    break
                else:
                    x = x.right
            else: 
                if x.left == self.__nil:
                    break
                else:
                    x = x.left
                
        if z.val >= x.val:
            z.parent = x
            x.right = z
        else:
            z.parent = x
            x.left = z
        # 保持红黑树性质
        z.color = 'R' 
        self.__InsertFixUp(z)
    
    def delete(self, num):
        '''
        Delete a node
        '''
        x = self.root
        while x.val != num and x != self.__nil:
            if num > x.val:
                x = x.right
            else:
                x = x.left
        # 没有该元素
        assert x!=self.__nil, 'This element is not in RBTree.'
        # 应该要考虑根节点被删除的情况
        # 删除节点
        flag = x.is_black()
        y = None # 记录需要修正的节点
        if x.left == self.__nil and x.right == self.__nil:
            # 删除根节点
            if x == self.root:
                self.root = None  
            # 删除叶子节点
            elif x.parent.left == x:
                x.parent.left = self.__nil
                # 回收内存
                #del x
            else:
                x.parent.right = self.__nil
                #del x

        elif x.left == self.__nil and x.right != self.__nil:
            y = x.right
            # 删除根节点
            if x == self.root:
                self.root = x.right
                x.right.parent = None
            elif x.parent.left == x:
                x.right.parent = x.parent
                x.parent.left = x.right
            else:
                x.right.parent = x.parent
                x.parent.right = x.right
            #del x
        elif x.left != self.__nil and x.right == self.__nil:
            y = x.left
            if x == self.root:
                self.root = x.left
                x.left.parent = None
            elif x.parent.left == x:
                x.left.parent = x.parent
                x.parent.left = x.left
            else:
                x.left.parent = x.parent
                x.parent.right = x.left
            #del x
            
        elif x.left != self.__nil and x.right != self.__nil:
            # 寻找中序后继节点代替 x
            flag = 0 # 这种情况不用修正
            y = x.right
            while y.left != self.__nil:
                y = y.left
            # 值拷贝
            t = y.val
            self.delete(t)
            x.val = t
            
        # 红黑树性质保持
        if flag == 1 and y != None:
            # 如果删去黑色节点
            self.__DeleteFixUp(y)
    
    def leftrotate(self,x):
        '''
        Left rotate the x node.
        '''
        parent = x.parent
        y = x.right
        y.parent = parent
        if parent != None:          
            if parent.left == x:
                parent.left = y
            else:
                parent.right = y
        else:
            self.root = y
        x.right = y.left
        if y.left != None:
            y.left.parent = x
        y.left = x
        x.parent = y
    
    def rightrotate(self,y):
        '''
        Right rotate the root.
        '''
        parent = y.parent
        x = y.left
        x.parent = parent
        if parent != None:

            if parent.left == y:
                parent.left = x
            else:
                parent.right = x
        else:
            self.root = x
        y.left = x.right
        if x.right != None:
            x.right.parent = y
        x.right = y
        y.parent = x
        
    def __DeleteFixUp(self,x):
        # 8 cases
        if x.color == 'R':
            x.color = 'B'
        else:
            # x 是双黑节点
            if x != self.root:
                if x == x.parent.left:
                    if x.parent.right.color == 'R':
                        # case1: brother is red
                        self.__Delete_case1(x)
                    elif x.parent.right.left.color == 'B' and x.parent.right.right.color == 'B':
                        # case2: brother's children are black
                        self.__Delete_case2(x)
                    elif x.parent.right.left.color == 'R' and x.parent.right.right.color == 'B':
                        # case3:
                        self.__Delete_case3(x)
                    elif x.parent.right.right.color == 'R':
                        # case4:
                        self.__Delete_case4(x)
                elif x == x.parent.right:
                    if x.parent.left.color == 'R':
                        # case5:
                        self.__Delete_case5(x)
                    elif x.parent.left.left.color == 'B' and x.parent.left.right.color == 'B':
                        # case6:
                        self.__Delete_case6(x)
                    elif x.parent.left.right.color == 'R' and x.parent.left.left.color == 'B':
                        # case7: 兄弟节点的左孩子是黑，右孩子是红
                        self.__Delete_case7(x)
                    elif x.parent.left.left.color == 'R':
                        # case8: 兄弟的左孩子是红色
                        self.__Delete_case8(x)
    
    def __Delete_case1(self, x):
        x.parent.right.color = 'B'
        x.parent.color = 'R'
        self.leftrotate(x.parent)
        self.__DeleteFixUp(x)
        
    def __Delete_case2(self, x):
        x.parent.right.color = 'R'
        self.__DeleteFixUp(x.parent)
        
    def __Delete_case3(self, x):
        x.parent.right.left.color = 'B'
        x.parent.right.color = 'R'
        self.rightrotate(x.parent.right)
        self.__Delete_case4(x)
    
    def __Delete_case4(self, x):
        x.parent.right.color = x.parent.color
        x.parent.color = 'B'
        x.parent.right.right.color = 'B'
        self.leftrotate(x.parent)
    
    def __Delete_case5(self, x):
        x.parent.left.color = 'B'
        x.parent.color = 'R'
        self.rightrotate(x.parent)
        self.__DeleteFixUp(x)
        
    def __Delete_case6(self, x):
        x.parent.left.color = 'R'
        self.__DeleteFixUp(x.parent)
        
    def __Delete_case7(self, x):
        x.parent.left.right.color = 'B'
        x.parent.left.color = 'R'
        self.leftrotate(x.parent)
        self.__Delete_case8(x)
    
    def __Delete_case8(self, x):
        x.parent.left.color = x.parent.color
        x.parent.color = 'B'
        x.paretn.left.left.color = 'B'
        self.rightrotate(x.parent)
        
    def __InsertFixUp(self, z):
        if z == self.root:
            z.color = 'B' 
        # 6 cases
        elif z.parent.color == 'R':
            if z.parent == z.parent.parent.left:
                if z.parent.parent.right.color == 'R':
                    # case 1: when uncle is red
                    self.__Insert_case1(z)

                elif z.parent.parent.right.color == 'B' and z == z.parent.right:
                    # case 2: uncle black and right son
                    self.__Insert_case2(z)

                elif z.parent.parent.right.color == 'B' and z == z.parent.left:
                    # case 3: uncle black and left son
                    self.__Insert_case3(z)
                    
            elif z.parent == z.parent.parent.right:
                if z.parent.parent.left.color == 'R':
                    # case 4: when uncle is red
                    self.__Insert_case4(z)
                elif z.parent.parent.left.color == 'B' and z == z.parent.left:
                    self.__Insert_case5(z)
                elif z.parent.parent.left.color == 'B' and z == z.parent.right:
                    self.__Insert_case6(z)    
        
    def __Insert_case1(self, z):
        z.parent.color = 'B'
        z.parent.parent.right.color = 'B'
        z.parent.parent.color = 'R'
        self.__InsertFixUp(z.parent.parent)
    
    def __Insert_case2(self, z):
        z = z.parent
        self.leftrotate(z)
        self.__Insert_case3(z)
    
    def __Insert_case3(self, z):
        z.parent.color = 'B'
        z.parent.parent.color = 'R'
        self.rightrotate(z.parent.parent)
    
    def __Insert_case4(self, z):
        z.parent.color = 'B'
        z.parent.parent.left.color = 'B'
        z.parent.parent.color = 'R'
        self.__InsertFixUp(z.parent.parent)
    
    def __Insert_case5(self, z):
        z = z.parent
        self.rightrotate(z)
        self.__Insert_case6(z)
    
    def __Insert_case6(self, z):
        z.parent.color = 'B'
        z.parent.parent.color = 'R'
        self.leftrotate(z.parent.parent)
    